package com.lans.SortAlgorithm;

import java.util.Arrays;

/*
 * @author: lans
 * @date: 2025/1/20
 * @name: 刘宇
 */
public class QuickSort1 {
    public static void main(String[] args) {
        int[] arr = {1,4,12,325,41231231,3,2,432,3131,43245};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int startIndex,int endIndex) {
        //停止递归条件
        if(startIndex >= endIndex) {
            return;
        }
        int pIndex = partition(arr,startIndex,endIndex);
        quickSort(arr,startIndex,pIndex-1);
        quickSort(arr,pIndex+1,endIndex);
    }
    public static int partition(int[] arr, int startIndex, int endIndex) {
        int p = arr[startIndex];
        int l = startIndex;
        int r = endIndex;
        while(l!=r){
            while((r>l)&&(arr[r]>p)){
                r--;
            }
            while((l<r)&&(arr[l]<=p)){
                l++;
            }
            if(l<r){
                int temp = arr[l];
                arr[l]= arr[r];
                arr[r]=temp;
            }
        }
        //循环结束后,左侧都小于等于基准元素 右侧大于基准元素 交换基准元素
        arr[startIndex] = arr[l];
        arr[l] = p;
        return l;
    }
}
